﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 原题连接：https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=196&tqId=37562&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FtopicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=%E4%B8%BB%E6%8C%81%E4%BA%BA%E8%B0%83%E5%BA%A6

/*
题目描述：
有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。

数据范围:
1
≤
𝑛
≤
1
0
5
1≤n≤10
5
  ，
−
2
32
≤
𝑠
𝑡
𝑎
𝑟
𝑡
𝑖
≤
𝑒
𝑛
𝑑
𝑖
≤
2
31
−
1
−2
32
 ≤start
i
​
 ≤end
i
​
 ≤2
31
 −1

复杂度要求：时间复杂度
𝑂
(
𝑛
log
⁡
𝑛
)
O(nlogn) ，空间复杂度
𝑂
(
𝑛
)
O(n)
示例1
输入：
2,[[1,2],[2,3]]
复制
返回值：
1
复制
说明：
只需要一个主持人就能成功举办这两个活动
示例2
输入：
2,[[1,3],[2,4]]
复制
返回值：
2
复制
说明：
需要两个主持人才能成功举办这两个活动
备注：
1
≤
𝑛
≤
1
0
5
1≤n≤10
5

𝑠
𝑡
𝑎
𝑟
𝑡
𝑖
,
𝑒
𝑛
𝑑
𝑖
start
i
​
 ,end
i
​
 在int范围内
*/


// 开始解题：
// 方法——贪心 + 堆
class Solution {
public:
    // 核心思想：将所有的区间分成若干个“集合”，这些集合中的区间都是两两不相交的
    // 所以我们要求的答案就是这样的集合的最少个数
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        // 现将区间按照左端点排序
        sort(startEnd.begin(), startEnd.end(), [](const vector<int>& v1, const vector<int>& v2) {
            return v1[0] < v2[0];
            });
        // 因为我们判断两个区间是是否有重叠，只需要判断新区间的左端点和老区间的右端点是否有重合
        // 所以我们只需要存储每个集合最后一个区间的右端点
        priority_queue<int, vector<int>, greater<int>> heap;
        for (int i = 0; i < n; i++) {
            if (heap.empty()) {
                heap.push(startEnd[i][1]);
            }
            else {
                // 每次选择集合中最小的右端点，看看有没有重合
                int left = heap.top();
                if (left <= startEnd[i][0]) {
                    heap.pop();
                }
                heap.push(startEnd[i][1]);
            }
        }
        return heap.size();
    }
};